package algorithm7.leetcode.每日一题.YEAR2023.month5;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class DAY20230519_LC1079 {

    /**

     你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
     注意：本题中，每个活字字模只能使用一次。

     示例 1：
     输入："AAB"
     输出：8
     解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

     示例 2：
     输入："AAABBC"
     输出：188

     示例 3：
     输入："V"
     输出：1


     */
    public int numTilePossibilities(String tiles) {
        int len = tiles.length();
        Map<Character, Integer> count = new HashMap<>();
        for (char t : tiles.toCharArray()) {
            count.put(t, count.getOrDefault(t, 0) + 1);
        }
        Set<Character> tile = new HashSet<>(count.keySet());
        return handle1_dfs(0, len, count, tile) - 1;
    }

    private int handle1_dfs(int i, int len, Map<Character, Integer> count, Set<Character> tile) {
        if (i == len) {
            return 1;
        }
        int res = 1;
        for (Character ch : tile) {
            // 该字符还有剩余
            if (count.get(ch) > 0) {
                // 剩余数-1
                count.put(ch, count.get(ch) - 1);
                // 去下一个位置考虑
                res += handle1_dfs(i + 1, len, count, tile);
                // 回溯
                count.put(ch, count.get(ch) + 1);
            }
        }
        return res;
    }

    @Test
    void t1() {
        String tiles = "AAB";
        int res = numTilePossibilities(tiles);
        System.out.println("res = " + res);

    }


}
